package LiKou;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
 */
public class test3 {
    public static void main(String[] args) {
        String s = "a", t = "a";
        System.out.println(minWindow(s,t));
    }
    public static String minWindow(String s, String t) {
        if(s.length()<t.length()){
            return "";
        }
        int minLen=s.length()+1;
        int start=0;
        Map<Character,Integer> map=new HashMap<>();
        char[] sCharArray = s.toCharArray();
        char[] tCharArray = t.toCharArray();
        for(int i=0;i<tCharArray.length;i++){
            if(map.containsKey(tCharArray[i])){
                map.put(tCharArray[i],map.get(tCharArray[i])+1);
            }else{
                map.put(tCharArray[i],1);
            }
        }
        for(int left=0,right=0;right<s.length();right++){
            if(map.containsKey(sCharArray[right])){
                map.put(sCharArray[right],map.get(sCharArray[right])-1);
            }
            if(isHealthy(map)){
                while(isHealthy(map)){
                    if(map.containsKey(sCharArray[left]) && (map.get(sCharArray[left])<0)){
                        map.put(sCharArray[left],map.get(sCharArray[left])+1);
                        left++;
                    } else if (!map.containsKey(sCharArray[left])) {
                        left++;
                    } else{
                        break;
                    }
                }
                if((right-left+1)<minLen){
                    minLen=right-left+1;
                    start=left;
                }
            }
        }
        return minLen==s.length()+1?"":s.substring(start,start+minLen);
    }
    public static boolean isHealthy(Map<Character,Integer> map){
        for(Character i:map.keySet()){
            if(map.get(i)>0){
                return false;
            }
        }
        return true;
    }
}
